package Example_practice02;

public class LcsProblem {
    //动态规划求解最长公共子序列
    public static String LCS(String s1,String s2){
        int n=s1.length();
        int m=s2.length();
        s1=" "+s1;
        s2=" "+s2;//方便处理边界情况

        int[][] dp=new int[n+1][m+1];
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                //两字符串最后一个元素相同
                if (s1.charAt(i)==s2.charAt(j)){
                    //把前面以i-1结尾的最长公共子序列+结尾元素既是最长公共子序列
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        System.out.println("最长公共子序列的长度为："+dp[n][m]);

        //利用回溯法记录该最长公共子序列，返回给函数
        StringBuilder result=new StringBuilder();
        int i=n;
        int j=m;
        while (i>0&&j>0){
            if (s1.charAt(i)==s2.charAt(j)){
                //永远插在第一位，保证顺序
                result.insert(0,s1.charAt(i));
                i--;
                j--;
            }else {
                if (dp[i-1][j]>dp[i][j-1]){
                    i--;
                } else {
                    j--;
                }
            }
        }
        return result.toString();
    }
    public static void main(String[] args){
        String str1="QWEyui";
        String str2="QEpoiiui";
        System.out.println("最长公共子序列的为："+LCS(str1,str2));
    }
}